The aim of these studies is to determine whether patients with advanced malignant melanoma have a greater number of, and more durable, responses to treatment with a combination of Interleukin 2 and chemotherapy than either of these agents alone. Patients with Stage 11 and 111 measurable disease receive sequential chemotherapy followed by Interleukin 2 and are then followed for response and survival.